from typing import List


class Item:
    value: any
    priority: int
    index: int

    def __init__(self, value, priority, index = -1):
        self.value = value
        self.priority = priority
        self.index = index

    def __str__(self) -> str:
        return f"Item: {self.value}:{self.priority}"

    def __repr__(self) -> str:
        return self.__str__()


class PopItem:
    item: Item
    delta: int

    def __init__(self, item, delta) -> None:
        self.item = item
        self.delta = delta


class PriorityQueue:
    """小顶堆优先级队列"""
    __data__: List[Item]

    def __init__(self, qsize: int):
        self.qsize = qsize
        self.__data__ = [0]

    def get_data(self) -> List[Item]:
        return self.__data__[1:]

    def len(self):
        return len(self.__data__) - 1

    def less(self, i: int ,j: int):
        return self.__data__[i].priority < self.__data__[j].priority

    def swap(self, i: int, j: int):
        self.__data__[i], self.__data__[j] = self.__data__[j], self.__data__[i]
        self.__data__[i].index, self.__data__[j].index = self.__data__[j].index, self.__data__[i].index

    def heapify_up(self, i: int):
        """指定节点从下向上堆化"""
        while True:
            j = int(i / 2)  # 父节点下标
            if j == 0:
                break
            if j > 0 and self.less(i, j):  # 当前节点优先级小于父节点优先级
                self.swap(i, j)
            i = j

    def heapify_down(self, i: int):
        """指定节点从上向下堆化"""
        max_idx = self.len()  # 最大下标值
        while True:
            j1 = 2 * i  # 左子节点下标
            if j1 > max_idx:  # 完全二叉树，左子节点不存在，右子节点必定不存在
                break
            j2 = j1 + 1  # 右子节点下标
            j = j1
            if j2 <= max_idx:
                if self.less(j2, j1):
                    j = j2
            if self.less(j, i):  # 左子节点或右子节点小于当前节点
                self.swap(j, i)
            i = j

    def insert(self, x: Item) -> bool:
        """新增元素"""
        size = self.len()
        if size >= self.qsize:
            return False
        x.index = size
        self.__data__.append(x)
        self.heapify_up(self.len())
        return True

    def remove(self, i: int):
        """移除下标为i的元素"""
        self.__data__[i], self.__data__[-1] = self.__data__[-1], self.__data__[i]
        self.__data__[i].index = self.__data__[-1].index
        self.__data__.pop()
        self.heapify_down(i)

    def pop(self) -> Item:
        """删除堆顶元素"""
        if self.len() == 0:
            return None
        item = self.__data__[1]
        self.remove(1)
        return item

    def peek_and_shif(self, p: int) -> PopItem:
        """弹出堆顶优先级大于p的元素"""
        if self.len() == 0:
            return PopItem(None, 0)
        item = self.__data__[1]
        if item.priority > p:
            return PopItem(None, (item.priority - p) / 1000)
        self.pop()
        return PopItem(item, 0)


if __name__ == "__main__":
    h = PriorityQueue()
    data = [33,27,21,16,13,15,9,5,6,7,8,1,2]
    for x in data:
        h.insert(Item(x, x))
    print(h.get_data())
    h.insert(Item(22, 22))
    print(h.get_data())

    h = PriorityQueue()
    data = [33,27,21,16,13,15,19,5,6,7,8,1,2,12]
    for x in data:
        h.insert(Item(x, x))
    print(h.get_data())
    h.pop()
    print(h.get_data())
    item = h.peek_and_shif(25)
    print(h.get_data(), item.item, item.delta)
    item = h.peek_and_shif(27)
    print(h.get_data(), item.item, item.delta)
